/**
 * @file: associative_array.cpp
 * Implementation of associative array
 */ 
/**
 * Copyright 2013 MIPT-COMPILER team
 */
#pragma once

#include <iostream>
#include <list>

using namespace std;

template <class ValueType, class KeyType>
class Array
{
public:
    struct elem
    {
        ValueType value;
        KeyType key;
    };
    Array(){};
    ~Array(){};
    bool check_key ( const KeyType& k ) const;
    bool insert ( const KeyType& k, const ValueType& it );
    const ValueType& find ( const KeyType& k ) const;
    ValueType& find ( const KeyType& k );
    bool remove ( const KeyType& k );
    const ValueType& operator[] ( const KeyType& k ) const;
    ValueType& operator[] ( const KeyType& k );
private:
    list< elem > container;
};

class ExceptionFind {};
class ExceptionConstFind {};
class ExceptionOperator {};

template < class ValueType, class KeyType >
bool Array<ValueType, KeyType>::check_key ( const KeyType& k ) const
{
    typename list< elem >::const_iterator it; 
    it  = container.begin();
    for ( it; it != container.end(); ++it )
        if ( (*it).key == k )
            return ( false );
    return ( true );
};

template < class ValueType, class KeyType >
bool Array<ValueType, KeyType>::insert ( const KeyType& k, const ValueType& i )
{
    if ( this->check_key ( k ) )
    {
        elem el;
        el.key = k;
        el.value = i;
        container.push_back ( el );
        return ( true );
    }
    else return ( false );
};
template < class ValueType, class KeyType >
ValueType& Array<ValueType, KeyType>::find ( const KeyType& k )
{
    typename list< elem >:: iterator it;
    it = container.begin();
    for (it; it != container.end(); ++it)
        if ( (*it).key == k)
            return (*it).value;
    throw ExceptionFind();
};

template < class ValueType, class KeyType >
const ValueType& Array<ValueType, KeyType>::find ( const KeyType& k ) const
{
    typename list< elem >::const_iterator it;
    it = container.begin();
    for( it; it != container.end(); ++it )
        if ( (*it).key == k )
            return (*it).value;
    throw ExceptionConstFind();
};

template < class ValueType, class KeyType >
bool Array<ValueType, KeyType>::remove ( const KeyType& k )
{    
    typename list< elem >::iterator it;
    it = container.begin();
    for ( it; it != container.end(); ++it )
        if ( (*it).key == k )
        {
            container.erase ( it );
            return ( true );
        }
    return ( false );

};

template < class ValueType, class KeyType >
const ValueType& Array<ValueType, KeyType>::operator[] ( const KeyType& k)  const
{
    if ( this -> check_key ( k ) )
        return this -> find ( k );
    else throw ExceptionOperator();
};
template < class ValueType, class KeyType >
ValueType& Array<ValueType, KeyType>::operator[] ( const KeyType& k )
{
    if ( this -> check_key ( k ) )
    {
        return this -> find ( k );
    }
    else
    {
        ValueType sub_item;
        insert ( k, sub_item );
        return this -> find (k);
    }
};

